package com.solution.greed;

public class Solution {

    /*
        贪心算法，找出当前条件下局部最优解，双指针
    */
    public int jump(int[] nums) {
        int step, current_reach, next_max_node;
        step = 0;
        current_reach = 0;  // 当前节点最大可以跳跃到的节点
        next_max_node = 0;  // 上一次设置的最大节点
        // 迭代当前层可跳跃距离
        for ( int i = 0 ; i < nums.length ; i++ ) {
            // 如果当前节点跳跃步数超过next_max_node
            if ( i > next_max_node ) {
                next_max_node = current_reach;
                step++;
            }
            current_reach = max(current_reach, i + nums[i]);
        }
        return step;
    }

    public int max(int a, int b) {
        if ( a > b )
            return a;
        return b;
    }

}
